<TITLE>prob017: Ramsey numbers</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob017: Ramsey numbers</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Results </H3>

Stanislaw Radziszowski has written an 
<a href=http://www.combinatorics.org/Surveys/ds1.ps>up-to-date survey</a>
for all types of Ramsey numbers.

<P>
The special case of R(k,k) numbers has attracted perhaps the
most attention. R(4,4) has been shown to equal 18. R(5,5) is
only known to lie between 43 and 49. This is a very difficult
combinatorial problem.

<P>
Erdos related the following anecdote: "Aliens invade the earth and 
threaten to obliterate it in a year's time unless human beings can find 
the Ramsey number for red five and blue five [that is, R(5,5)]. We could
marshal the world's best minds and fastest computers, and within a year we 
could probably calculate the value. If the aliens demanded the Ramsey number 
for red six and blue six, however, we would have no choice but to launch a 
preemptive attack. (Graham, Ronald L. and Joel H. Spencer. Ramsey Theory. Scientific American July 1990: 112-117).


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


